home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1994 January / PSL Monthly Shareware CD-ROM (Public Software Library) (January 1994).iso / games / dos / puzzles / ibmmaze.com / IBMMAZE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-11  |  43.0 KB  |  1,166 lines
  1. /*
  2.          This program will generate a three dimensional maze suitable for
  3.     printing on any printer that can print IBM graphics character 219.  A
  4.     different random number seed will produce a different maze.
  5.  
  6.          Written by James L. Dean
  7.                     406 40th Street
  8.                     New Orleans, LA 70124-1532
  9. */
  10.  
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <malloc.h>
  15. #include <conio.h>
  16. #include <math.h>
  17.  
  18. #define TRUE 1
  19. #define FALSE 0
  20.  
  21. #define PAGE_WIDTH_IN_INCHES    8.0 /* LENGTH OF A LINE OF PRINT */
  22. #define PAGE_WIDTH_IN_SPACES   80
  23. #define WIDTH_IN_PAGES          6
  24. #define WIDTH_IN_INCHES        48.0 /* WIDTH_IN_PAGES*PAGE_WIDTH_IN_INCHES */
  25. #define NUM_Y_DOTS            480   /* WIDTH_IN_PAGES*PAGE_WIDTH_IN_SPACES */
  26. #define Y_DOT_MAX             479   /* NUM_Y_DOTS-1 */
  27. #define PAGE_LENGTH_IN_INCHES  11.0
  28. #define PAGE_LENGTH_IN_SPACES  66
  29. #define LENGTH_IN_PAGES         6
  30. #define LENGTH_IN_INCHES       66.0 /* LENGTH_IN_PAGES*PAGE_LENGTH_IN_INCHES */
  31. #define NUM_X_DOTS            396   /* LENGTH_IN_PAGES*PAGE_LENGTH_IN_SPACES */
  32. #define X_DOT_MAX             395   /* NUM_X_DOTS-1 */
  33. #define MIN_DOTS_PER_ROOM_WALL 40
  34. #define NUM_COLUMNS             9 /* <= NUM_X_DOTS/MIN_DOTS_PER_ROOM_WALL */
  35. #define MAX_X                  18 /* 2*NUM_COLUMNS */
  36. #define MAX_X_PLUS_1           19 /* MAX_X+1 */
  37. #define NUM_ROWS               12 /* <= NUM_Y_DOTS/MIN_DOTS_PER_ROOM_WALL */
  38. #define MAX_Y                  24 /* 2*NUM_ROWS */
  39. #define MAX_Y_PLUS_1           25 /* MAX_Y+1 */
  40. #define NUM_ROOMS_IN_MAZE     108 /* NUM_COLUMNS*NUM_ROWS */
  41.  
  42. typedef struct pointtype_record
  43.           {
  44.             int x;
  45.             int y;
  46.           } pointtype;
  47.  
  48. typedef struct prime_rec_record  *prime_rec_ptr;
  49.  
  50. typedef struct prime_rec_record
  51.           {
  52.             double        x;
  53.             double        y;
  54.             double        z;
  55.             char          base_z;
  56.             prime_rec_ptr left;
  57.             prime_rec_ptr right;
  58.             prime_rec_ptr down;
  59.             prime_rec_ptr lesser_x;
  60.             prime_rec_ptr greater_x;
  61.           } prime_rec;
  62.  
  63. typedef struct stack_rec_record  *stack_rec_ptr;
  64.  
  65. typedef struct stack_rec_record
  66.           {
  67.             char          index_1;
  68.             char          index_2;
  69.             stack_rec_ptr next_ptr;
  70.           } stack_rec;
  71.  
  72. typedef struct up_rec_record    *up_rec_ptr;
  73.  
  74. typedef struct up_rec_record
  75.           {
  76.             prime_rec_ptr up;
  77.             up_rec_ptr    next;
  78.             up_rec_ptr    previous;
  79.           } up_rec;
  80.  
  81. static void   add_room(void);
  82. static void   adjust_perspective(prime_rec_ptr *,prime_rec_ptr *,
  83.                prime_rec_ptr *,double *,double *,double *,double *,double *,
  84.                int *);
  85. static void   draw_line(int *,int *,int *,int *,int);
  86. static void   evaluate_and_transform(double *,double *,double *,double *,int *,
  87.                int *,double *,double *,prime_rec_ptr *,prime_rec_ptr *,
  88.                prime_rec_ptr *,double *,double *,double *,double *,double *,
  89.                int *);
  90. static double f(double,double);
  91.        void   main(void);
  92. static void   plot(prime_rec_ptr *,double *,double *,double *,double *,int *,
  93.                int *,double *,FILE **);
  94. static void   pset(int *,int *,int);
  95.  
  96. static int           delta_x [4] [24];
  97. static int           delta_y [4] [24];
  98. static unsigned char *line_ptr [NUM_X_DOTS];
  99. static char          page [MAX_Y_PLUS_1] [MAX_X_PLUS_1];
  100. static int           r_n [8];
  101. static int           r_n_index_1;
  102. static int           r_n_index_2;
  103. static int           tem_int;
  104. static int           x;
  105. static double        x_max;
  106. static int           x_next;
  107. static int           x_wall;
  108. static int           y;
  109. static int           y_next;
  110. static int           y_wall;
  111.  
  112. void main(void)
  113.     {
  114.       static   double        aspect_ratio;
  115.       static   int           column_num;
  116.       static   int           delta_index_1a;
  117.       static   int           delta_index_1b;
  118.       static   int           delta_index_1c;
  119.       static   int           delta_index_1d;
  120.       static   int           delta_index_2;
  121.       static   int           digit;
  122.       static   int           digit_num;
  123.       static   int           ending_column;
  124.       static   int           fatal_error;
  125.       static   int           line_num;
  126.       static   int           max_y_out;
  127.       static   int           max_z_out;
  128.                FILE          *maze;
  129.       static   int           num_x_divisions;
  130.       static   int           num_y_divisions;
  131.       static   int           page_num;
  132.       static   prime_rec_ptr prime_cornor;
  133.       static   prime_rec_ptr prime_head;
  134.       static   prime_rec_ptr prime_ptr;
  135.       static   prime_rec_ptr prime_tail;
  136.       static   double        rotation;
  137.       static   unsigned char *row_ptr;
  138.       static   char          seed [256];
  139.       static   int           seed_length;
  140.       static   int           starting_column;
  141.       static   int           sum;
  142.       static   double        tilt;
  143.       static   double        x_min;
  144.       static   int           x_out;
  145.       static   double        x_prime_max;
  146.       static   double        y_max;
  147.       static   double        y_min;
  148.       static   int           y_out;
  149.       static   double        y_prime_max;
  150.       static   double        y_prime_min;
  151.       static   double        z_prime_max;
  152.       static   double        z_prime_min;
  153.                              
  154.       fatal_error=FALSE;
  155.       printf("\n     This program takes a \"photograph\" of a three ");
  156.       printf("dimensional maze.  A printer\n");
  157.       printf("that can print IBM graphics character number 219 is ");
  158.       printf("necessary to print the\n");
  159.       printf("photograph from its \"negative\".\n");
  160.       printf("\n     Random number seed? ");
  161.       fflush(stdin);
  162.       gets(&seed[0]);
  163.       seed_length=strlen(&seed[0]);
  164.       for (r_n_index_1=0; r_n_index_1 < seed_length; ++r_n_index_1)
  165.         {
  166.           tem_int=(int) seed[r_n_index_1];
  167.           while (tem_int >= 29)
  168.            tem_int-=29;
  169.           r_n[r_n_index_1]=tem_int;
  170.         }
  171.       r_n_index_2=7;
  172.       while (r_n_index_1 > 0)
  173.         {
  174.            r_n_index_1--;
  175.            r_n[r_n_index_2]=r_n[r_n_index_1];
  176.            r_n_index_2--;
  177.         }
  178.       while (r_n_index_2 >= 0)
  179.         {
  180.           r_n[r_n_index_2]=19;
  181.           r_n_index_2--;
  182.         }
  183.       printf("\n     Designing floor plan...\n");
  184.       delta_x[0][0]=-1;
  185.       delta_y[0][0]=0;
  186.       delta_x[1][0]=0;
  187.       delta_y[1][0]=1;
  188.       delta_x[2][0]=1;
  189.       delta_y[2][0]=0;
  190.       delta_x[3][0]=0;
  191.       delta_y[3][0]=-1;
  192.       delta_index_2=0;
  193.       for (delta_index_1a=0; delta_index_1a < 4; ++delta_index_1a)
  194.         for (delta_index_1b=0; delta_index_1b < 4; ++delta_index_1b)
  195.           if (delta_index_1a != delta_index_1b)
  196.             for (delta_index_1c=0; delta_index_1c < 4; ++delta_index_1c)
  197.               if ((delta_index_1a != delta_index_1c)
  198.               &&  (delta_index_1b != delta_index_1c))
  199.                 for (delta_index_1d=0; delta_index_1d < 4; ++delta_index_1d)
  200.                   if ((delta_index_1a != delta_index_1d)
  201.                   &&  (delta_index_1b != delta_index_1d)
  202.                   &&  (delta_index_1c != delta_index_1d))
  203.                     {
  204.                       delta_x[delta_index_1a][delta_index_2]=delta_x[0][0];
  205.                       delta_y[delta_index_1a][delta_index_2]=delta_y[0][0];
  206.                       delta_x[delta_index_1b][delta_index_2]=delta_x[1][0];
  207.                       delta_y[delta_index_1b][delta_index_2]=delta_y[1][0];
  208.                       delta_x[delta_index_1c][delta_index_2]=delta_x[2][0];
  209.                       delta_y[delta_index_1c][delta_index_2]=delta_y[2][0];
  210.                       delta_x[delta_index_1d][delta_index_2]=delta_x[3][0];
  211.                       delta_y[delta_index_1d][delta_index_2]=delta_y[3][0];
  212.                       delta_index_2++;
  213.                     }
  214.       max_y_out=X_DOT_MAX;
  215.       max_z_out=Y_DOT_MAX;
  216.       aspect_ratio=1.0/(LENGTH_IN_INCHES
  217.        *(((float) NUM_Y_DOTS)/((float) NUM_X_DOTS))/WIDTH_IN_INCHES);
  218.       for (y_out=0; y_out <= MAX_Y; ++y_out)
  219.         for (x_out=0; x_out <= MAX_X; ++x_out)
  220.           page[y_out][x_out]='W';
  221.       sum=0;
  222.       for (digit_num=1; digit_num <= 3; ++digit_num)
  223.         {
  224.           digit=r_n[0];
  225.           r_n_index_1=0;
  226.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  227.             {
  228.               tem_int=r_n[r_n_index_2];
  229.               r_n[r_n_index_1]=tem_int;
  230.               digit+=tem_int;
  231.               if (digit >= 29)
  232.                  digit-=29;
  233.               r_n_index_1=r_n_index_2;
  234.             }
  235.           r_n[7]=digit;
  236.           sum=29*sum+digit;
  237.         }
  238.       x=2*(sum % NUM_COLUMNS)+1;
  239.       sum=0;
  240.       for (digit_num=1; digit_num <= 3; ++digit_num)
  241.         {
  242.           digit=r_n[0];
  243.           r_n_index_1=0;
  244.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  245.             {
  246.               tem_int=r_n[r_n_index_2];
  247.               r_n[r_n_index_1]=tem_int;
  248.               digit+=tem_int;
  249.               if (digit >= 29)
  250.                  digit-=29;
  251.               r_n_index_1=r_n_index_2;
  252.             }
  253.           r_n[7]=digit;
  254.           sum=29*sum+digit;
  255.         }
  256.       y=2*(sum % NUM_ROWS)+1;
  257.       add_room();
  258.       page[0][1]=' ';
  259.       page[MAX_Y][MAX_X-1]=' ';
  260.       printf("\n     Building maze...\n");
  261.       x_min=1.0;
  262.       x_max=(double) MAX_Y;
  263.       x_max=2.0*x_max+5.0;
  264.       y_min=1.0;
  265.       y_max=(double) MAX_X;
  266.       y_max=2.0*y_max+5.0;
  267.       num_x_divisions=2*MAX_Y+5;
  268.       num_y_divisions=2*MAX_X+5;
  269.       prime_head=NULL;
  270.       rotation=20.0;
  271.       tilt=30.0;
  272.       evaluate_and_transform(&x_min,&x_max,&y_min,&y_max,
  273.        &num_x_divisions,&num_y_divisions,&rotation,&tilt,
  274.        &prime_cornor,&prime_head,&prime_tail,&x_prime_max,
  275.        &y_prime_min,&y_prime_max,&z_prime_min,&z_prime_max,
  276.        &fatal_error);
  277.       if (! fatal_error)
  278.         {
  279.           printf("\n     Photographing maze...\n");
  280.           adjust_perspective(&prime_cornor,&prime_head,&prime_tail,
  281.            &x_prime_max,&y_prime_min,&y_prime_max,&z_prime_min,
  282.            &z_prime_max,&fatal_error);
  283.         }
  284.       if (! fatal_error)
  285.         {
  286.           printf("\n     Developing film...\n");
  287.           for (line_num=0;  
  288.            ((! fatal_error) && (line_num < NUM_X_DOTS)); 
  289.            line_num++)
  290.             if ((row_ptr=(unsigned char *) malloc(NUM_Y_DOTS))
  291.              == NULL)
  292.               {
  293.                 fatal_error=TRUE;
  294.                 printf("\n     Fatal error:  out of memory\n");
  295.               }
  296.             else
  297.               {
  298.                 line_ptr[line_num]=row_ptr;
  299.                 for (column_num=0; column_num < NUM_Y_DOTS; 
  300.                  column_num++)
  301.                   *(row_ptr++)=(unsigned char) ' ';
  302.               }
  303.         }
  304.       if (! fatal_error)
  305.         {
  306.           plot(&prime_tail,&y_prime_min,&y_prime_max,
  307.            &z_prime_min,&z_prime_max,&max_y_out,&max_z_out,
  308.            &aspect_ratio,&maze);
  309.           maze=fopen("IBMMAZE.LST","w");
  310.           starting_column=0;
  311.           ending_column=PAGE_WIDTH_IN_SPACES-1;
  312.           for (page_num=1; page_num <= WIDTH_IN_PAGES; page_num++)
  313.             {
  314.               for (line_num=0; (line_num < NUM_X_DOTS); line_num++)
  315.                 {
  316.                   for (column_num=starting_column;
  317.                    column_num <= ending_column; column_num++)
  318.                     fputc((int) *((line_ptr[line_num])+column_num),maze);
  319.                   fputc((int) '\n',maze);
  320.                 }
  321.               starting_column+=PAGE_WIDTH_IN_SPACES;
  322.               ending_column+=PAGE_WIDTH_IN_SPACES;
  323.             }
  324.           fclose(maze);
  325.           for (line_num=0; ((! fatal_error) && (line_num < NUM_X_DOTS)); 
  326.            line_num++)
  327.             free(line_ptr[line_num]);
  328.           while (prime_head != NULL)
  329.             {
  330.               prime_ptr=prime_head->greater_x;
  331.               free(prime_head);
  332.               prime_head=prime_ptr;
  333.             }
  334.         }
  335.       if (! fatal_error)
  336.         printf("\n     To print the maze, \"PRINT IBMMAZE.LST\".\n");
  337.     }
  338.  
  339. static void add_room()
  340.     {
  341.       unsigned char delta_index_1;
  342.       unsigned char delta_index_2;
  343.  
  344.       page[y][x]=' ';
  345.       delta_index_1=0;
  346.       do
  347.         {
  348.           delta_index_2=(unsigned char) r_n[0];
  349.           r_n_index_1=0;
  350.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  351.             {
  352.               tem_int=r_n[r_n_index_2];
  353.               r_n[r_n_index_1]=tem_int;
  354.               delta_index_2+=(unsigned char) tem_int;
  355.               if (delta_index_2 >= 29)
  356.                 delta_index_2-=29;
  357.               r_n_index_1=r_n_index_2;
  358.             }
  359.           r_n[7]=delta_index_2;
  360.         }
  361.       while (delta_index_2 >= 24);
  362.       while (delta_index_1 < 4)
  363.         {
  364.           x_next=x+2*delta_x[delta_index_1][delta_index_2];
  365.           if ((x_next <= 0) || (x_next >= MAX_X))
  366.             delta_index_1++;
  367.           else
  368.             {
  369.               y_next=y+2*delta_y[delta_index_1][delta_index_2];
  370.               if ((y_next <= 0) || (y_next >= MAX_Y))
  371.                 delta_index_1++;
  372.               else
  373.                 if ((page[y_next][x_next] == 'W'))
  374.                   {
  375.                     if (x == x_next)
  376.                       {
  377.                         y_wall=(y+y_next)/2;
  378.                         page[y_wall][x_next]=' ';
  379.                       }
  380.                     else
  381.                       {
  382.                         x_wall=(x+x_next)/2;
  383.                         page[y_next][x_wall]=' ';
  384.                       }
  385.                     x=x_next;
  386.                     y=y_next;
  387.                     add_room();
  388.                     x-=2*delta_x[delta_index_1][delta_index_2];
  389.                     y-=2*delta_y[delta_index_1][delta_index_2];
  390.                   }
  391.                 else
  392.                   delta_index_1++;
  393.             }
  394.         }
  395.     }
  396.  
  397. static double f(x,y)
  398.   double x;
  399.   double y;
  400.     {
  401.       register int    x_out;
  402.       register int    y_out;
  403.       static   double z;
  404.  
  405.       y_out=((int) x)-2;
  406.       if (y_out < 0)
  407.         z=0.0;
  408.       else
  409.         if (y_out > 2*MAX_Y+1)
  410.           z=0.0;
  411.         else
  412.           {
  413.             x_out=((int) y)-2;
  414.             if (x_out < 0)
  415.               z=0.0;
  416.             else
  417.               if (x_out > 2*MAX_X+1)
  418.                 z=0.0;
  419.               else
  420.                 if (page[y_out/2][x_out/2] == 'W')
  421.                   z=7.0;
  422.                 else
  423.                   z=0.0;
  424.           }
  425.       return(z);
  426.     }
  427.  
  428. static void evaluate_and_transform(x_min,x_max,y_min,y_max,num_x_divisions,
  429.  num_y_divisions,rotation,tilt,prime_cornor,prime_head,prime_tail,x_prime_max,
  430.  y_prime_min,y_prime_max,z_prime_min,z_prime_max,fatal_error)
  431.   double        *x_min;
  432.   double        *x_max;
  433.   double        *y_min;
  434.   double        *y_max;
  435.   int           *num_x_divisions;
  436.   int           *num_y_divisions;
  437.   double        *rotation;
  438.   double        *tilt;
  439.   prime_rec_ptr *prime_cornor;
  440.   prime_rec_ptr *prime_head;
  441.   prime_rec_ptr *prime_tail;
  442.   double        *x_prime_max;
  443.   double        *y_prime_min;
  444.   double        *y_prime_max;
  445.   double        *z_prime_min;
  446.   double        *z_prime_max;
  447.   int           *fatal_error;
  448.     {
  449.       static   double        cos_rotation;
  450.       static   double        cos_tilt;
  451.       static   double        delta_x;
  452.       static   double        delta_y;
  453.       static   prime_rec_ptr last_prime_ptr;
  454.       static   prime_rec_ptr prime_ptr;
  455.       static   double        radians;
  456.       static   double        radians_per_degree;
  457.       static   prime_rec_ptr left;
  458.       static   double        sin_rotation;
  459.       static   double        sin_tilt;
  460.       static   up_rec_ptr    up_head;
  461.       static   up_rec_ptr    up_ptr;
  462.       static   up_rec_ptr    up_tail;
  463.       static   double        x;
  464.       register int           x_division_num;
  465.       static   double        y;
  466.       register int           y_division_num;
  467.       static   double        x_rotated;
  468.       static   double        z;
  469.  
  470.       radians_per_degree=atan((double) 1.0)/45.0;
  471.       radians=(*tilt)*radians_per_degree;
  472.       cos_tilt=cos(radians);
  473.       sin_tilt=sin(radians);
  474.       radians=(*rotation)*radians_per_degree;
  475.       cos_rotation=cos(radians);
  476.       sin_rotation=sin(radians);
  477.       z=f(*x_min,*y_min);
  478.       x_rotated=(*x_min)*cos_rotation+(*y_min)*sin_rotation;
  479.       (*y_prime_min)=-(*x_min)*sin_rotation+(*y_min)*cos_rotation;
  480.       (*z_prime_min)=-x_rotated*sin_tilt+z*cos_tilt;
  481.       (*x_prime_max)=x_rotated*cos_tilt+z*sin_tilt;
  482.       (*y_prime_max)=(*y_prime_min);
  483.       (*z_prime_max)=(*z_prime_min);
  484.       last_prime_ptr=NULL;
  485.       delta_x=(double) (*num_x_divisions);
  486.       delta_x=((*x_max)-(*x_min))/delta_x;
  487.       delta_y=(double) (*num_y_divisions);
  488.       delta_y=((*y_max)-(*y_min))/delta_y;
  489.       up_head=NULL;
  490.       up_tail=NULL;
  491.       for (y_division_num=1;
  492.        ((y_division_num <= (*num_y_divisions)) && (! *fatal_error));
  493.        ++y_division_num)
  494.         {
  495.           if ((up_ptr=(up_rec *) malloc(sizeof(up_rec))) == NULL)
  496.             {
  497.               *fatal_error=TRUE;
  498.               printf("\n     Fatal error:  out of memory\n");
  499.             }
  500.           else
  501.             {
  502.               up_ptr->up=NULL;
  503.               if (up_head == NULL)
  504.                 {
  505.                   up_head=up_ptr;
  506.                   up_ptr->previous=NULL;
  507.                 }
  508.               else
  509.                 {
  510.                   up_tail->next=up_ptr;
  511.                   up_ptr->previous=up_tail;
  512.                 }
  513.               up_ptr->next=NULL;
  514.               up_tail=up_ptr;
  515.             }
  516.         }
  517.       x=(*x_min);
  518.       for (x_division_num=1;
  519.        ((x_division_num <= (*num_x_divisions)) && (! *fatal_error));
  520.        ++x_division_num)
  521.         {
  522.           left=NULL;
  523.           up_ptr=up_head;
  524.           y=(*y_min);
  525.           for (y_division_num=1;
  526.            ((y_division_num <= (*num_y_divisions)) && (! *fatal_error));
  527.            ++y_division_num)
  528.             {
  529.               z=f(x,y);
  530.               if ((prime_ptr=(prime_rec *) malloc(sizeof(prime_rec)))
  531.                == NULL)
  532.                 {
  533.                   *fatal_error=TRUE;
  534.                   printf("\n     Fatal error:  out of memory\n");
  535.                 }
  536.               else
  537.                 {
  538.                   prime_ptr->left=left;
  539.                   if (z > 0.0)
  540.                     prime_ptr->base_z=(char) 1;
  541.                   else
  542.                     prime_ptr->base_z=(char) 0;
  543.                   if (left != NULL)
  544.                     left->right=prime_ptr;
  545.                   if (up_ptr->up != NULL)
  546.                     up_ptr->up->down=prime_ptr;
  547.                   x_rotated=x*cos_rotation+y*sin_rotation;
  548.                   prime_ptr->y=-x*sin_rotation+y*cos_rotation;
  549.                   prime_ptr->x=x_rotated*cos_tilt+z*sin_tilt;
  550.                   prime_ptr->z=-x_rotated*sin_tilt+z*cos_tilt;
  551.                   if (prime_ptr->x > (*x_prime_max))
  552.                     (*x_prime_max)=prime_ptr->x;
  553.                   if (prime_ptr->y < (*y_prime_min))
  554.                     (*y_prime_min)=prime_ptr->y;
  555.                   if (prime_ptr->y > (*y_prime_max))
  556.                     (*y_prime_max)=prime_ptr->y;
  557.                   if (prime_ptr->z < (*z_prime_min))
  558.                     (*z_prime_min)=prime_ptr->z;
  559.                   if (prime_ptr->z > (*z_prime_max))
  560.                     (*z_prime_max)=prime_ptr->z;
  561.                   prime_ptr->lesser_x=NULL;
  562.                   if (last_prime_ptr == NULL)
  563.                     {
  564.                       (*prime_tail)=prime_ptr;
  565.                       (*prime_cornor)=prime_ptr;
  566.                       prime_ptr->greater_x=NULL;
  567.                     }
  568.                   else
  569.                     {
  570.                       (*prime_head)->lesser_x=prime_ptr;
  571.                       prime_ptr->greater_x=(*prime_head);
  572.                     }
  573.                   (*prime_head)=prime_ptr;
  574.                   left=prime_ptr;
  575.                   up_ptr->up=prime_ptr;
  576.                   up_ptr=up_ptr->next;
  577.                   last_prime_ptr=prime_ptr;
  578.                   y+=delta_y;
  579.                 }
  580.             }
  581.           if (! *fatal_error)
  582.             {
  583.               left->right=NULL;
  584.               x+=delta_x;
  585.             }
  586.         }
  587.       if (! *fatal_error)
  588.         while (up_head != NULL)
  589.           {
  590.             up_head->up->down=NULL;
  591.             up_ptr=up_head->next;
  592.             free(up_head);
  593.             up_head=up_ptr;
  594.           }
  595.     }
  596.  
  597. static void adjust_perspective(prime_cornor,prime_head,prime_tail,x_prime_max,
  598.  y_prime_min,y_prime_max,z_prime_min,z_prime_max,fatal_error)
  599.   prime_rec_ptr *prime_cornor;
  600.   prime_rec_ptr *prime_head;
  601.   prime_rec_ptr *prime_tail;
  602.   double        *x_prime_max;
  603.   double        *y_prime_min;
  604.   double        *y_prime_max;
  605.   double        *z_prime_min;
  606.   double        *z_prime_max;
  607.   int           *fatal_error;
  608.     {
  609.       static   double        delta_x;
  610.       static   double        delta_y;
  611.       static   double        delta_z;
  612.       register int           finished;
  613.       static   prime_rec_ptr last_prime_ptr;
  614.       static   prime_rec_ptr left;
  615.       static   prime_rec_ptr new_prime_head;
  616.       static   prime_rec_ptr new_prime_ptr;
  617.       static   prime_rec_ptr new_prime_tail;
  618.       static   prime_rec_ptr next_prime_row;
  619.       static   prime_rec_ptr prime_column;
  620.       static   prime_rec_ptr prime_ptr;
  621.       static   prime_rec_ptr prime_row;
  622.       static   up_rec_ptr    up_head;
  623.       static   up_rec_ptr    up_ptr;
  624.       static   up_rec_ptr    up_tail;
  625.       static   double        x_eye;
  626.       static   double        y_center;
  627.       static   double        z_center;
  628.  
  629.       if (((*y_prime_max)-(*y_prime_min)) > ((*z_prime_max)-(*z_prime_min)))
  630.         x_eye=2.0*((*y_prime_max)-(*y_prime_min))+(*x_prime_max);
  631.       else
  632.         x_eye=2.0*((*z_prime_max)-(*z_prime_min))+(*x_prime_max);
  633.       if (x_eye != (*x_prime_max))
  634.         {
  635.           up_head=NULL;
  636.           up_tail=NULL;
  637.           prime_column=(*prime_cornor);
  638.           while ((prime_column != NULL) && (! *fatal_error))
  639.             {
  640.               if ((up_ptr=(up_rec *) malloc(sizeof(up_rec))) == NULL)
  641.                 {
  642.                   *fatal_error=TRUE;
  643.                   printf("\n     Fatal error:  out of memory\n");
  644.                 }
  645.               else
  646.                 {
  647.                   up_ptr->up=NULL;
  648.                   if (up_head == NULL)
  649.                     {
  650.                       up_head=up_ptr;
  651.                       up_ptr->previous=NULL;
  652.                     }
  653.                   else
  654.                     {
  655.                       up_tail->next=up_ptr;
  656.                       up_ptr->previous=up_tail;
  657.                     }
  658.                   up_ptr->next=NULL;
  659.                   up_tail=up_ptr;
  660.                   prime_column=prime_column->right;
  661.                 }
  662.             }
  663.           y_center=(double) ((*y_prime_max)+(*y_prime_min))/2.0;
  664.           z_center=(double) ((*z_prime_max)+(*z_prime_min))/2.0;
  665.           last_prime_ptr=NULL;
  666.           new_prime_head=NULL;
  667.           new_prime_tail=NULL;
  668.           prime_row=(*prime_cornor);
  669.           while ((prime_row != NULL) && (! *fatal_error))
  670.             {
  671.               left=NULL;
  672.               up_ptr=up_head;
  673.               next_prime_row=prime_row->down;
  674.               prime_column=prime_row;
  675.               while ((prime_column != NULL) && (! *fatal_error))
  676.                 {
  677.                   if ((new_prime_ptr=(prime_rec *) malloc(sizeof(prime_rec)))
  678.                    == NULL)
  679.                     {
  680.                       *fatal_error=TRUE;
  681.                       printf("\n     Fatal error:  out of memory\n");
  682.                     }
  683.                   else
  684.                     {
  685.                       new_prime_ptr->left=left;
  686.                       new_prime_ptr->base_z=prime_column->base_z;
  687.                       if (left != NULL)
  688.                         left->right=new_prime_ptr;
  689.                       if (up_ptr->up != NULL)
  690.                         up_ptr->up->down=new_prime_ptr;
  691.                       delta_x=prime_column->x-x_eye;
  692.                       delta_y=prime_column->y-y_center;
  693.                       delta_z=prime_column->z-z_center;
  694.                       new_prime_ptr->x
  695.                        =sqrt(delta_x*delta_x+delta_y*delta_y+delta_z*delta_z);
  696.                       new_prime_ptr->y
  697.                        =y_center+(double)(prime_column->y-y_center)
  698.                        *(x_eye-(*x_prime_max))/(x_eye-prime_column->x);
  699.                       new_prime_ptr->z
  700.                        =z_center+(double)(prime_column->z-z_center)
  701.                        *(x_eye-(*x_prime_max))/(x_eye-prime_column->x);
  702.                       if (last_prime_ptr == NULL)
  703.                         {
  704.                           new_prime_head=new_prime_ptr;
  705.                           new_prime_tail=new_prime_ptr;
  706.                           new_prime_ptr->lesser_x=NULL;
  707.                           new_prime_ptr->greater_x=NULL;
  708.                         }
  709.                       else
  710.                         if (new_prime_ptr->x < last_prime_ptr->x)
  711.                           {
  712.                             finished=FALSE;
  713.                             while (! finished)
  714.                               {
  715.                                 last_prime_ptr=last_prime_ptr->lesser_x;
  716.                                 if (last_prime_ptr == NULL)
  717.                                   finished=TRUE;
  718.                                 else
  719.                                   {
  720.                                     if (new_prime_ptr->x >= last_prime_ptr->x)
  721.                                       finished=TRUE;
  722.                                   }
  723.                               }
  724.                             new_prime_ptr->lesser_x=last_prime_ptr;
  725.                             if (last_prime_ptr == NULL)
  726.                               {
  727.                                 new_prime_head->lesser_x=new_prime_ptr;
  728.                                 new_prime_ptr->greater_x=new_prime_head;
  729.                                 new_prime_head=new_prime_ptr;
  730.                               }
  731.                             else
  732.                               {
  733.                                 new_prime_ptr->greater_x
  734.                                  =last_prime_ptr->greater_x;
  735.                                 last_prime_ptr->greater_x->lesser_x
  736.                                  =new_prime_ptr;
  737.                                 last_prime_ptr->greater_x=new_prime_ptr;
  738.                               }
  739.                           }
  740.                         else
  741.                           {
  742.                             finished=FALSE;
  743.                             while (! finished)
  744.                               {
  745.                                 last_prime_ptr=last_prime_ptr->greater_x;
  746.                                 if (last_prime_ptr == NULL)
  747.                                   finished=TRUE;
  748.                                 else
  749.                                   {
  750.                                     if (new_prime_ptr->x <= last_prime_ptr->x)
  751.                                       finished=TRUE;
  752.                                   }
  753.                               }
  754.                             new_prime_ptr->greater_x=last_prime_ptr;
  755.                             if (last_prime_ptr == NULL)
  756.                               {
  757.                                 new_prime_tail->greater_x=new_prime_ptr;
  758.                                 new_prime_ptr->lesser_x=new_prime_tail;
  759.                                 new_prime_tail=new_prime_ptr;
  760.                               }
  761.                             else
  762.                               {
  763.                                 new_prime_ptr->lesser_x
  764.                                  =last_prime_ptr->lesser_x;
  765.                                 last_prime_ptr->lesser_x->greater_x
  766.                                  =new_prime_ptr;
  767.                                 last_prime_ptr->lesser_x=new_prime_ptr;
  768.                               }
  769.                           }
  770.                     }
  771.                   if (! *fatal_error)
  772.                     {
  773.                       left=new_prime_ptr;
  774.                       up_ptr->up=new_prime_ptr;
  775.                       up_ptr=up_ptr->next;
  776.                       last_prime_ptr=new_prime_ptr;
  777.                       prime_ptr=prime_column->right;
  778.                       free(prime_column);
  779.                       prime_column=prime_ptr;
  780.                     }
  781.                 }
  782.               if (! *fatal_error)
  783.                 {
  784.                   left->right=NULL;
  785.                   prime_row=next_prime_row;
  786.                 }
  787.             }
  788.           if (! *fatal_error)
  789.             {
  790.               (*prime_head)=new_prime_head;
  791.               (*prime_tail)=new_prime_tail;
  792.               while (up_head != NULL)
  793.                 {
  794.                   up_head->up->down=NULL;
  795.                   up_ptr=up_head->next;
  796.                   free(up_head);
  797.                   up_head=up_ptr;
  798.                 }
  799.             }
  800.         }
  801.     }
  802.  
  803. static void pset(x,y,shading)
  804.   int *x;
  805.   int *y;
  806.   int shading;
  807.     {
  808.       static int dot;
  809.  
  810.       switch (shading)
  811.         {
  812.           case 0:
  813.             switch ((*y) % 4)
  814.               {
  815.                 case 0:
  816.                   if (((*x) % 4) == 3)
  817.                     dot=TRUE;
  818.                   else
  819.                     dot=FALSE;
  820.                   break;
  821.                 case 1:
  822.                   if (((*x) % 4) == 1)
  823.                     dot=TRUE;
  824.                   else
  825.                     dot=FALSE;
  826.                   break;
  827.                 case 2:
  828.                   if (((*x) % 4) == 2)
  829.                     dot=TRUE;
  830.                   else
  831.                     dot=FALSE;
  832.                   break;
  833.                 default:
  834.                   if (((*x) % 4) == 0)
  835.                     dot=TRUE;
  836.                   else
  837.                     dot=FALSE;
  838.                   break;
  839.               }
  840.             break;
  841.           case 1:
  842.             if ((*y) % 2)
  843.               if (((*x) % 4) == 1)
  844.                 dot=TRUE;
  845.               else
  846.                 dot=FALSE;
  847.             else
  848.               if ((*x) % 2)
  849.                 dot=FALSE;
  850.               else
  851.                 dot=TRUE;
  852.             break;
  853.           case 2:
  854.             if ((*y) % 2)
  855.               if ((*x) % 2)
  856.                 dot=TRUE;
  857.               else
  858.                 dot=FALSE;
  859.             else
  860.               if ((*x) % 2)
  861.                 dot=FALSE;
  862.               else
  863.                 dot=TRUE;
  864.             break;
  865.           default:
  866.             dot=TRUE;
  867.             break;
  868.         };
  869.       if (dot)
  870.         *((line_ptr[*x])+(Y_DOT_MAX-(*y)))=(unsigned char) 219;
  871.       else
  872.         *((line_ptr[*x])+(Y_DOT_MAX-(*y)))=(unsigned char) ' ';
  873.     }
  874.  
  875. static void draw_line(x1,y1,x2,y2,shading)
  876.   int *x1;
  877.   int *y1;
  878.   int *x2;
  879.   int *y2;
  880.   int shading;
  881.     {
  882.       static   int error;
  883.       static   int error_prime_x;
  884.       static   int error_prime_y;
  885.       register int permissible_delta_x;
  886.       register int permissible_delta_y;
  887.       static   int x;
  888.       static   int x_diff;
  889.       static   int y;
  890.       static   int y_diff;
  891.  
  892.       if ((*x2) >= (*x1))
  893.         permissible_delta_x=1;
  894.       else
  895.         permissible_delta_x=-1;
  896.       if ((*y2) >= (*y1))
  897.         permissible_delta_y=1;
  898.       else
  899.         permissible_delta_y=-1;
  900.       x=(*x1);
  901.       y=(*y1);
  902.       x_diff=(*x2)-(*x1);
  903.       y_diff=(*y2)-(*y1);
  904.       error=0;
  905.       pset(&x,&y,shading);
  906.       while ((x != (*x2)) || (y != (*y2)))
  907.         {
  908.           error_prime_x=error+permissible_delta_x*y_diff;
  909.           error_prime_y=error-permissible_delta_y*x_diff;
  910.           if (abs(error_prime_x) <= abs(error_prime_y))
  911.             {
  912.               x+=permissible_delta_x;
  913.               error=error_prime_x;
  914.             }
  915.           else
  916.             {
  917.               y+=permissible_delta_y;
  918.               error=error_prime_y;
  919.             }
  920.           pset(&x,&y,shading);
  921.         }
  922.     }
  923.  
  924. static void plot(prime_tail,y_prime_min,y_prime_max,z_prime_min,z_prime_max,
  925.  max_y_out,max_z_out,aspect_ratio,maze)
  926.   prime_rec_ptr *prime_tail;
  927.   double *y_prime_min;
  928.   double *y_prime_max;
  929.   double *z_prime_min;
  930.   double *z_prime_max;
  931.   int    *max_y_out;
  932.   int    *max_z_out;
  933.   double *aspect_ratio;
  934.   FILE   **maze;
  935.     {
  936.       static   pointtype     box [4];
  937.       static   long          box_delta_x;
  938.       static   long          box_delta_y;
  939.       register int           box_num_1;
  940.       register int           box_num_2;
  941.       static   long          box_x_intercept;
  942.       static   int           box_x1;
  943.       static   int           box_x2;
  944.       static   int           box_y_max;
  945.       static   int           box_y_min;
  946.       static   long          box_y_offset;
  947.       static   int           box_y1;
  948.       static   int           intercept_count_mod_2;
  949.       static   int           line_x1;
  950.       static   int           line_x2;
  951.       static   int           line_y1;
  952.       static   int           line_y2;
  953.       static   double        pixels_per_unit;
  954.       static   prime_rec_ptr prime_ptr;
  955.       static   int           shading;
  956.       static   double        y_offset;
  957.       static   double        y_out_max;
  958.       static   double        z_offset;
  959.       static   double        z_out_max;
  960.  
  961.       y_out_max=(double) (*max_y_out);
  962.       z_out_max=(double) (*max_z_out);
  963.       if ((*aspect_ratio)*z_out_max*((*y_prime_max)-(*y_prime_min))
  964.        > y_out_max*((*z_prime_max)-(*z_prime_min)))
  965.         {
  966.           pixels_per_unit
  967.            =y_out_max/((*aspect_ratio)*((*y_prime_max)-(*y_prime_min)));
  968.           y_offset=0.0;
  969.           z_offset
  970.            =-(z_out_max-pixels_per_unit*((*z_prime_max)-(*z_prime_min)))/2.0;
  971.         }
  972.       else
  973.         if ((*aspect_ratio)*z_out_max*((*y_prime_max)-(*y_prime_min))
  974.          < y_out_max*((*z_prime_max)-(*z_prime_min)))
  975.           {
  976.             pixels_per_unit=z_out_max/((*z_prime_max)-(*z_prime_min));
  977.             y_offset=(y_out_max
  978.              -(*aspect_ratio)*pixels_per_unit*((*y_prime_max)-(*y_prime_min)))/2.0;
  979.             z_offset=0.0;
  980.           }
  981.         else
  982.           /* plot degenerates to a single point */
  983.           {
  984.             pixels_per_unit=1.0;
  985.             y_offset=y_out_max/2.0;
  986.             z_offset=-z_out_max/2.0;
  987.           }
  988.       prime_ptr=(*prime_tail);
  989.       while ((prime_ptr != NULL))
  990.         {
  991.           if ((prime_ptr->right != NULL))
  992.             {
  993.               if ((prime_ptr->down != NULL))
  994.                 {
  995.                   box[0].x=(int) (y_offset+pixels_per_unit
  996.                    *(*aspect_ratio)*(prime_ptr->y-(*y_prime_min)));
  997.                   box[0].y=(int) (z_offset+z_out_max-pixels_per_unit
  998.                    *(prime_ptr->z-(*z_prime_min)));
  999.                   box[1].x=(int) (y_offset+pixels_per_unit
  1000.                    *(*aspect_ratio)*(prime_ptr->right->y-(*y_prime_min)));
  1001.                   box[1].y=(int) (z_offset+z_out_max-pixels_per_unit
  1002.                    *(prime_ptr->right->z-(*z_prime_min)));
  1003.                   box[3].x=(int) (y_offset+pixels_per_unit
  1004.                    *(*aspect_ratio)*(prime_ptr->down->y-(*y_prime_min)));
  1005.                   box[3].y=(int) (z_offset+z_out_max-pixels_per_unit
  1006.                    *(prime_ptr->down->z-(*z_prime_min)));
  1007.                   box[2].x=(int) (y_offset+pixels_per_unit
  1008.                    *(*aspect_ratio)*(prime_ptr->down->right->y-(*y_prime_min)));
  1009.                   box[2].y=(int) (z_offset+z_out_max-pixels_per_unit
  1010.                    *(prime_ptr->down->right->z-(*z_prime_min)));
  1011.                   box_y_min=box[0].y;
  1012.                   box_y_max=box_y_min;
  1013.                   if ((prime_ptr->base_z == (char) 1)
  1014.                   &&  (prime_ptr->right->base_z == (char) 1)
  1015.                   &&  (prime_ptr->down->base_z == (char) 1)
  1016.                   &&  (prime_ptr->down->right->base_z == (char) 1)) 
  1017.                     shading=0;
  1018.                   else
  1019.                     if ((prime_ptr->base_z == (char) 0)
  1020.                     &&  (prime_ptr->right->base_z == (char) 0)
  1021.                     &&  (prime_ptr->down->base_z == (char) 0)
  1022.                     &&  (prime_ptr->down->right->base_z == (char) 0)) 
  1023.                       shading=1;
  1024.                     else
  1025.                       if ((prime_ptr->base_z == (char) 1)
  1026.                       &&  (prime_ptr->right->base_z == (char) 1)
  1027.                       &&  (prime_ptr->down->base_z == (char) 0)
  1028.                       &&  (prime_ptr->down->right->base_z == (char) 0)) 
  1029.                         shading=2;
  1030.                       else
  1031.                         if ((prime_ptr->base_z == (char) 1)
  1032.                         &&  (prime_ptr->right->base_z == (char) 0)
  1033.                         &&  (prime_ptr->down->base_z == (char) 1)
  1034.                         &&  (prime_ptr->down->right->base_z == (char) 0)) 
  1035.                           shading=3;
  1036.                         else
  1037.                           if ((prime_ptr->down->down == NULL)
  1038.                           &&  (prime_ptr->base_z == (char) 0)) 
  1039.                             shading=1;
  1040.                           else
  1041.                             shading=2;
  1042.                   for (box_num_1=1; box_num_1 < 4; ++box_num_1)
  1043.                     {
  1044.                       if (box[box_num_1].y < box_y_min)
  1045.                         box_y_min=box[box_num_1].y;
  1046.                       if (box[box_num_1].y > box_y_max)
  1047.                         box_y_max=box[box_num_1].y;
  1048.                     }
  1049.                   for (box_y1=box_y_min; box_y1 <= box_y_max; ++box_y1)
  1050.                     {
  1051.                       intercept_count_mod_2=0;
  1052.                       box_num_2=1;
  1053.                       for (box_num_1=0; box_num_1 < 4; ++box_num_1)
  1054.                         {
  1055.                           if (box[box_num_1].y >= box_y1)
  1056.                             {
  1057.                               if (box_y1 > box[box_num_2].y)
  1058.                                 {
  1059.                                   box_delta_y=box[box_num_2].y-box[box_num_1].y;
  1060.                                   box_delta_x=box[box_num_2].x-box[box_num_1].x;
  1061.                                   box_y_offset=box_y1-box[box_num_1].y;
  1062.                                   box_x_intercept=box[box_num_1].x;
  1063.                                   box_x1=(int) ((box_delta_x*box_y_offset)
  1064.                                    /box_delta_y+box_x_intercept);
  1065.                                   if (intercept_count_mod_2 == 0)
  1066.                                     box_x2=box_x1;
  1067.                                   else
  1068.                                     {
  1069.                                       if (box_x1 < box_x2)
  1070.                                         {
  1071.                                           line_x1=box_x1;
  1072.                                           line_x2=box_x2;
  1073.                                         }
  1074.                                       else
  1075.                                         {
  1076.                                           line_x1=box_x2;
  1077.                                           line_x2=box_x1;
  1078.                                         }
  1079.                                       pset(&line_x1,&box_y1,shading);
  1080.                                       while (line_x1 < line_x2)
  1081.                                         {
  1082.                                           line_x1++;
  1083.                                           pset(&line_x1,&box_y1,shading);
  1084.                                         }
  1085.                                     }
  1086.                                   intercept_count_mod_2=1-intercept_count_mod_2;
  1087.                                 }
  1088.                             }
  1089.                           else
  1090.                             {
  1091.                               if (box_y1 <= box[box_num_2].y)
  1092.                                 {
  1093.                                   box_delta_y=box[box_num_2].y-box[box_num_1].y;
  1094.                                   box_delta_x=box[box_num_2].x-box[box_num_1].x;
  1095.                                   box_y_offset=box_y1-box[box_num_1].y;
  1096.                                   box_x_intercept=box[box_num_1].x;
  1097.                                   box_x1=(int) ((box_delta_x*box_y_offset)
  1098.                                    /box_delta_y+box_x_intercept);
  1099.                                   if (intercept_count_mod_2 == 0)
  1100.                                     box_x2=box_x1;
  1101.                                   else
  1102.                                     {
  1103.                                       if (box_x1 < box_x2)
  1104.                                         {
  1105.                                           line_x1=box_x1;
  1106.                                           line_x2=box_x2;
  1107.                                         }
  1108.                                       else
  1109.                                         {
  1110.                                           line_x1=box_x2;
  1111.                                           line_x2=box_x1;
  1112.                                         }
  1113.                                       pset(&line_x1,&box_y1,shading);
  1114.                                       while (line_x1 < line_x2)
  1115.                                         {
  1116.                                           line_x1++;
  1117.                                           pset(&line_x1,&box_y1,shading);
  1118.                                         }
  1119.                                     }
  1120.                                   intercept_count_mod_2=1-intercept_count_mod_2;
  1121.                                 }
  1122.                             }
  1123.                           box_num_2++;
  1124.                           if (box_num_2 >= 4)
  1125.                             box_num_2=0;
  1126.                         }
  1127.                     }
  1128.                   box_num_2=1;
  1129.                   for (box_num_1=0; box_num_1 < 4; ++box_num_1)
  1130.                     {
  1131.                       line_x1=box[box_num_1].x;
  1132.                       line_y1=box[box_num_1].y;
  1133.                       line_x2=box[box_num_2].x;
  1134.                       line_y2=box[box_num_2].y;
  1135.                       box_num_2++;
  1136.                       draw_line(&line_x1,&line_y1,&line_x2,&line_y2,shading);
  1137.                       if (box_num_2 >= 4)
  1138.                         box_num_2=0;
  1139.                     }
  1140.                   if ((prime_ptr->base_z == (char) 1)
  1141.                   &&  (prime_ptr->right->base_z == (char) 1)
  1142.                   &&  (prime_ptr->down->base_z == (char) 0)
  1143.                   &&  (prime_ptr->down->right->base_z == (char) 0)) 
  1144.                     {
  1145.                       if (prime_ptr->left != NULL)
  1146.                         {
  1147.                           if (prime_ptr->left->base_z == (char) 0)
  1148.                             {
  1149.                               shading=0;
  1150.                               line_x1=box[0].x;
  1151.                               line_y1=box[0].y;
  1152.                               line_x2=box[3].x;
  1153.                               line_y2=box[3].y;
  1154.                               draw_line(&line_x1,&line_y1,&line_x2,&line_y2,
  1155.                                shading);
  1156.                             }
  1157.                         }
  1158.                     }
  1159.                 }
  1160.              }
  1161.            prime_ptr=prime_ptr->lesser_x;
  1162.         }
  1163.     }
  1164. 
  1165.  
  1166.